/**
 * 希尔排序
 * 将数组分成多个子数组，分别进行插入排序。初始时，选取一个递减的间隔值 gap（通常为数组长度的一半），然后按照这个间隔将数组分成若干组。
 * 然后对每组分别进行插入排序，不断缩小间隔值，直到间隔值为 1，完成最后一次插入排序。
 * 希尔排序的关键在于选择合适的间隔序列，不同的间隔序列会影响算法的性能。经过一系列的实验和研究，确定了一些间隔序列，例如希尔序列（1，4，13，40，121...）。
 */

function shellSort(arr) {
  const n = arr.length;
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; i++) {
      let temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
}

const arr = [10, 8, 7, 5, 4, 6, 3, 2, 1, 9];

shellSort(arr);
console.log("🌺", arr);
